public class Solution1370 {
    public String sortString(String s) {
        int[] f=new int[26];
        for (char c : s.toCharArray()) {
            f[c-'a']++;
        }
        int[] d={1,-1};
        int t=0;
        int cur=0;
        StringBuilder stringBuilder=new StringBuilder();
        while (stringBuilder.length()!=s.length()){
            if (f[cur]!=0){
                stringBuilder.append((char)(cur+'a'));
                f[cur]--;
            }
            cur=cur+d[t];
            if (cur>=26 || cur<0){
                t=1-t;
                cur=cur+d[t];
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution1370().sortString("aaaabbbbcccc"));
    }
}
